use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use std::ptr;

/// 无锁队列 (Michael & Scott算法)
pub struct LockFreeQueue<T> {
    head: AtomicPtr<Node<T>>,
    tail: AtomicPtr<Node<T>>,
}

/// 无锁栈 (Treiber栈)
pub struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
}

/// 无锁哈希表
pub struct LockFreeHashMap<K, V> {
    buckets: Vec<AtomicPtr<Entry<K, V>>>,
    len: AtomicUsize,
}

/// 无锁引用计数器
pub struct LockFreeRefCounter {
    count: AtomicUsize,
}

/// 无锁环形缓冲区
pub struct LockFreeRingBuffer<T> {
    buffer: Vec<AtomicPtr<T>>,
    head: AtomicUsize,
    tail: AtomicUsize,
    size: usize,
}

/// 节点结构
struct Node<T> {
    data: T,
    next: AtomicPtr<Node<T>>,
}

/// 哈希表条目
struct Entry<K, V> {
    key: K,
    value: V,
    next: AtomicPtr<Entry<K, V>>,
}

impl<T> LockFreeQueue<T> {
    pub fn new() -> Self {
        let dummy = Box::into_raw(Box::new(Node {
            data: unsafe { std::mem::MaybeUninit::uninit().assume_init() },
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        LockFreeQueue {
            head: AtomicPtr::new(dummy),
            tail: AtomicPtr::new(dummy),
        }
    }

    pub fn enqueue(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        loop {
            let tail = self.tail.load(Ordering::Acquire);
            let tail_ref = unsafe { &*tail };
            let next = tail_ref.next.load(Ordering::Acquire);

            if next.is_null() {
                if tail_ref
                    .next
                    .compare_exchange(next, new_node, Ordering::Release, Ordering::Relaxed)
                    .is_ok()
                {
                    let _ = self.tail.compare_exchange(
                        tail,
                        new_node,
                        Ordering::Release,
                        Ordering::Relaxed,
                    );
                    break;
                }
            } else {
                let _ = self.tail.compare_exchange(
                    tail,
                    next,
                    Ordering::Release,
                    Ordering::Relaxed,
                );
            }
        }
    }

    pub fn dequeue(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            let head_ref = unsafe { &*head };
            let next = head_ref.next.load(Ordering::Acquire);

            if next.is_null() {
                return None;
            }

            let next_ref = unsafe { &*next };
            let data = unsafe { ptr::read(&next_ref.data) };

            if self
                .head
                .compare_exchange(head, next, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                unsafe { let _ = Box::from_raw(head); }
                return Some(data);
            }
        }
    }

    pub fn len(&self) -> usize {
        let mut count = 0;
        let mut current = unsafe { &*self.head.load(Ordering::Acquire) };
        
        while let Some(next) = unsafe { current.next.load(Ordering::Acquire).as_ref() } {
            count += 1;
            current = next;
        }
        count
    }
}

impl<T> Drop for LockFreeQueue<T> {
    fn drop(&mut self) {
        while self.dequeue().is_some() {}
        let head = self.head.load(Ordering::Relaxed);
        if !head.is_null() {
            unsafe { let _ = Box::from_raw(head); }
        }
    }
}

impl<T> LockFreeStack<T> {
    pub fn new() -> Self {
        LockFreeStack {
            head: AtomicPtr::new(ptr::null_mut()),
        }
    }

    pub fn push(&self, data: T) {
        let new_node = Box::into_raw(Box::new(Node {
            data,
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        loop {
            let head = self.head.load(Ordering::Acquire);
            unsafe { (*new_node).next.store(head, Ordering::Relaxed); }

            if self
                .head
                .compare_exchange(head, new_node, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                break;
            }
        }
    }

    pub fn pop(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            if head.is_null() {
                return None;
            }

            let head_ref = unsafe { &*head };
            let next = head_ref.next.load(Ordering::Acquire);
            let data = unsafe { ptr::read(&head_ref.data) };

            if self
                .head
                .compare_exchange(head, next, Ordering::Release, Ordering::Relaxed)
                .is_ok()
            {
                unsafe { let _ = Box::from_raw(head); }
                return Some(data);
            }
        }
    }

    pub fn len(&self) -> usize {
        let mut count = 0;
        let mut current = self.head.load(Ordering::Acquire);
        
        while let Some(node) = unsafe { current.as_ref() } {
            count += 1;
            current = node.next.load(Ordering::Acquire);
        }
        count
    }
}

impl<K, V> LockFreeHashMap<K, V> 
where
    K: Eq + Clone + std::hash::Hash,
    V: Clone,
{
    pub fn new() -> Self {
        let mut buckets = Vec::with_capacity(16);
        for _ in 0..16 {
            buckets.push(AtomicPtr::new(ptr::null_mut()));
        }

        LockFreeHashMap {
            buckets,
            len: AtomicUsize::new(0),
        }
    }

    fn hash(&self, key: &K) -> usize {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::Hasher;
        
        let mut hasher = DefaultHasher::new();
        key.hash(&mut hasher);
        let hash_value = hasher.finish() as usize;
        hash_value % self.buckets.len()
    }
    
    pub fn insert(&self, key: K, value: V) {
        let bucket_index = self.hash(&key);
        let new_entry = Box::into_raw(Box::new(Entry {
            key: key.clone(),
            value,
            next: AtomicPtr::new(ptr::null_mut()),
        }));

        loop {
            let mut current = self.buckets[bucket_index].load(Ordering::Acquire);
            let mut prev: *mut Entry<K, V> = ptr::null_mut();

            while !current.is_null() {
                let entry = unsafe { &*current };
                if entry.key == key {
                    unsafe {
                        ptr::write(&mut (*current).value, (*new_entry).value.clone());
                        let _ = Box::from_raw(new_entry);
                    }
                    return;
                }
                prev = current;
                current = entry.next.load(Ordering::Acquire);
            }

            unsafe { (*new_entry).next.store(current, Ordering::Relaxed); }

            if prev.is_null() {
                if self.buckets[bucket_index]
                    .compare_exchange(current, new_entry, Ordering::Release, Ordering::Relaxed)
                    .is_ok()
                {
                    self.len.fetch_add(1, Ordering::Relaxed);
                    break;
                }
            } else {
                unsafe {
                    let _ = (*prev).next.compare_exchange(
                        current,
                        new_entry,
                        Ordering::Release,
                        Ordering::Relaxed,
                    );
                }
                self.len.fetch_add(1, Ordering::Relaxed);
                break;
            }
        }
    }

    pub fn get(&self, key: &K) -> Option<V> {
        let bucket_index = self.hash(key);
        let mut current = self.buckets[bucket_index].load(Ordering::Acquire);

        while !current.is_null() {
            let entry = unsafe { &*current };
            if entry.key == *key {
                return Some(entry.value.clone());
            }
            current = entry.next.load(Ordering::Acquire);
        }

        None
    }

    pub fn len(&self) -> usize {
        self.len.load(Ordering::Relaxed)
    }

    pub fn delete(&self, key: &K) -> Option<V> {
        let bucket_index = self.hash(key);
        let mut current = self.buckets[bucket_index].load(Ordering::Acquire);
        let mut prev: *mut Entry<K, V> = ptr::null_mut();

        while !current.is_null() {
            let entry = unsafe { &*current };
            if entry.key == *key {
                let next = entry.next.load(Ordering::Acquire);
                
                if prev.is_null() {
                    if self.buckets[bucket_index]
                        .compare_exchange(current, next, Ordering::Release, Ordering::Relaxed)
                        .is_ok()
                    {
                        self.len.fetch_sub(1, Ordering::Relaxed);
                        return Some(unsafe { Box::from_raw(current).value });
                    }
                } else {
                    let success = unsafe {
                        (*prev).next.compare_exchange(
                            current,
                            next,
                            Ordering::Release,
                            Ordering::Relaxed,
                        ).is_ok()
                    };
                    
                    if success {
                        self.len.fetch_sub(1, Ordering::Relaxed);
                        return Some(unsafe { Box::from_raw(current).value });
                    }
                }
                
                // 如果CAS失败，重新开始循环
                current = self.buckets[bucket_index].load(Ordering::Acquire);
                prev = ptr::null_mut();
                continue;
            }
            
            prev = current;
            current = entry.next.load(Ordering::Acquire);
        }

        None
    }
}

impl LockFreeRefCounter {
    pub fn new(initial: usize) -> Self {
        LockFreeRefCounter {
            count: AtomicUsize::new(initial),
        }
    }

    /// 增加引用计数
    pub fn increment(&self) -> usize {
        self.count.fetch_add(1, Ordering::Relaxed)
    }

    /// 减少引用计数
    pub fn decrement(&self) -> usize {
        self.count.fetch_sub(1, Ordering::Relaxed)
    }

    /// 获取当前计数
    pub fn get(&self) -> usize {
        self.count.load(Ordering::Relaxed)
    }

    /// 检查是否为0
    pub fn is_zero(&self) -> bool {
        self.count.load(Ordering::Relaxed) == 0
    }
}

impl<T> LockFreeRingBuffer<T> {
    pub fn new(size: usize) -> Self {
        let mut buffer = Vec::with_capacity(size);
        for _ in 0..size {
            buffer.push(AtomicPtr::new(ptr::null_mut()));
        }

        LockFreeRingBuffer {
            buffer,
            head: AtomicUsize::new(0),
            tail: AtomicUsize::new(0),
            size,
        }
    }

    /// 入队
    pub fn enqueue(&self, item: T) -> bool {
        let new_item = Box::into_raw(Box::new(item));
        let tail = self.tail.load(Ordering::Relaxed);
        let next_tail = (tail + 1) % self.size;

        if next_tail == self.head.load(Ordering::Relaxed) {
            return false; // 缓冲区满
        }

        self.buffer[tail].store(new_item, Ordering::Release);
        self.tail.store(next_tail, Ordering::Release);
        true
    }

    /// 出队
    pub fn dequeue(&self) -> Option<T> {
        let head = self.head.load(Ordering::Relaxed);

        if head == self.tail.load(Ordering::Relaxed) {
            return None; // 缓冲区空
        }

        let item = self.buffer[head].load(Ordering::Acquire);
        if item.is_null() {
            return None;
        }

        self.buffer[head].store(ptr::null_mut(), Ordering::Release);
        self.head.store((head + 1) % self.size, Ordering::Release);

        let data = unsafe { ptr::read(&*item) };
        unsafe { let _ = Box::from_raw(item); }
        Some(data)
    }

    /// 获取长度
    pub fn len(&self) -> usize {
        let head = self.head.load(Ordering::Relaxed);
        let tail = self.tail.load(Ordering::Relaxed);
        if tail >= head {
            tail - head
        } else {
            self.size - head + tail
        }
    }

    /// 是否为空
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// 是否满
    pub fn is_full(&self) -> bool {
        self.len() == self.size - 1
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::thread;
    use std::sync::Arc;

    #[test]
    fn test_lock_free_queue() {
        let queue = LockFreeQueue::new();
        
        queue.enqueue(1);
        queue.enqueue(2);
        
        assert_eq!(queue.dequeue(), Some(1));
        assert_eq!(queue.dequeue(), Some(2));
        assert_eq!(queue.dequeue(), None);
    }

    #[test]
    fn test_lock_free_stack() {
        let stack = LockFreeStack::new();
        
        stack.push(1);
        stack.push(2);
        
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert_eq!(stack.pop(), None);
    }

    #[test]
    fn test_lock_free_hash_map() {
        let map = LockFreeHashMap::new();
        
        map.insert("key1", "value1");
        map.insert("key2", "value2");
        
        assert_eq!(map.get(&"key1"), Some("value1"));
        assert_eq!(map.get(&"key2"), Some("value2"));
        assert_eq!(map.get(&"key3"), None);
    }

    #[test]
    fn test_lock_free_ref_counter() {
        let counter = LockFreeRefCounter::new(0);
        
        counter.increment();
        counter.increment();
        assert_eq!(counter.get(), 2);
        
        counter.decrement();
        assert_eq!(counter.get(), 1);
    }

    #[test]
    fn test_lock_free_ring_buffer() {
        let buffer = LockFreeRingBuffer::new(3);
        
        assert!(buffer.enqueue(1));
        assert!(buffer.enqueue(2));
        
        // 检查当前长度
        assert_eq!(buffer.len(), 2);
        
        // 出队一个元素，再入队
        assert_eq!(buffer.dequeue(), Some(1));
        assert!(buffer.enqueue(3));
        
        assert_eq!(buffer.dequeue(), Some(2));
        assert_eq!(buffer.dequeue(), Some(3));
        assert_eq!(buffer.dequeue(), None);
    }

    #[test]
    fn test_concurrent_queue() {
        let queue = Arc::new(LockFreeQueue::new());
        let mut handles = vec![];

        for i in 0..10 {
            let queue = queue.clone();
            handles.push(thread::spawn(move || {
                queue.enqueue(i);
            }));
        }

        for handle in handles {
            handle.join().unwrap();
        }

        let mut results = vec![];
        while let Some(item) = queue.dequeue() {
            results.push(item);
        }

        assert_eq!(results.len(), 10);
    }
}